package com.leetcode.www;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * Creared with IntelliJ IDEA.
 * Description:给出一个字符串数组words 组成的一本英语词典。返回words 中最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。
 *
 * 若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-word-in-dictionary
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-03-17
 * Time:11:14
 */
public class Everyday720 {
    public String longestWord(String[] words) {
        if(words == null)return null;
        Arrays.sort(words,(a, b)->{
            if(a.length() != b.length()){
                return a.length() - b.length();
            }else{
                return b.compareTo(a);
            }
        });//按字典顺序排列
        Set<String> set = new HashSet<>();
        String result = "";
        set.add("");
        for(int i = 0;i < words.length;i ++){
            String w = words[i];
            if(set.contains(w.substring(0,w.length() - 1))){//每一个单词都是由前面的单词逐渐构成的
                set.add(w);
                result = w;
            }
        }
        return result;
    }
}
